This paper presents a new algorithm, termed \emph{truncated amplitude flow}(TAF), to recover an unknown vector $\bm{x}$ from a system of quadraticequations of the form $y_i=|\langle\bm{a}_i,\bm{x}\rangle|^2$, where$\bm{a}_i$'s are given random measurement vectors. This problem is known to be\emph{NP-hard} in general. We prove that as soon as the number of equations ison the order of the number of unknowns, TAF recovers the solution exactly (upto a global unimodular constant) with high probability and complexity growinglinearly with both the number of unknowns and the number of equations. Our TAFapproach adopts the \emph{amplitude-based} empirical loss function, andproceeds in two stages. In the first stage, we introduce an\emph{orthogonality-promoting} initialization that can be obtained with a fewpower iterations. Stage two refines the initial estimate by successive updatesof scalable \emph{truncated generalized gradient iterations}, which are able tohandle the rather challenging nonconvex and nonsmooth amplitude-based objectivefunction. In particular, when vectors $\bm{x}$ and $\bm{a}_i$'s arereal-valued, our gradient truncation rule provably eliminates erroneouslyestimated signs with high probability to markedly improve upon its untruncatedversion. Numerical tests using synthetic data and real images demonstrate thatour initialization returns more accurate and robust estimates relative tospectral initializations. Furthermore, even under the same initialization, theproposed amplitude-based refinement outperforms existing Wirtinger flowvariants, corroborating the superior performance of TAF over state-of-the-artalgorithms.
展开▼
